#include <stdlib.h>

#define EXTRA_INFO_SZ 4
#define _EXTRA_INFO_ALIGN 4
#define EXTRA_INFO_ALIGN (_EXTRA_INFO_ALIGN-1)
#define EXTRA_INFO_TOTAL (EXTRA_INFO_SZ + _EXTRA_INFO_ALIGN)

#define alignPtr(ptr,align) ( ((size_t)(ptr) + (align)) & ~(size_t)(align) )

typedef struct
{
  char *base;
  char *mem;
  unsigned int totalSz;
  unsigned int usedSz;
  unsigned int align;
} stackMem;

stackMem *createStackMem(int startSz, int align)
{
  stackMem *sm = (stackMem *)malloc(sizeof(stackMem));

  align -= 1;
  sm->base = (char *)malloc(startSz+align);
  sm->mem = alignPtr(sm->base,align);
  sm->totalSz = startSz;
  sm->usedSz = 0;
  sm->align = align;

  return sm;
}

#define copyMem(dst, src, sz) memmove(dst,src,sz);
/*
void copyMem(char *dst, char *src, unsigned int sz)
{
  int i;

  if(dst<src) {
    for(i=0; i<sz; i++) dst[i] = src[i];
  } else {
    for(i=sz-1; i>=0; i--) dst[i] = src[i];
  }
}
*/

void *alloc(stackMem *sm, int sz)
{
  int freeMem = sm->totalSz - sm->usedSz;
  if(freeMem < (sz+EXTRA_INFO_TOTAL)) {
    sm->totalSz += (sz+EXTRA_INFO_TOTAL) - freeMem;
    char *newBase = (char *)realloc(sm->base, sm->totalSz+sm->align);
    if(newBase!=sm->base) {
      char *newMem = (char *)alignPtr(newBase,sm->align);

      unsigned long oldOffset = ((unsigned long)sm->mem) - ((unsigned long)sm->base);

      if( newMem!=(newBase+oldOffset) ) copyMem(newMem, newBase+oldOffset, sm->usedSz);
      sm->base = newBase;
      sm->mem = newMem;
    }
  }

  char *result = sm->mem+sm->usedSz;

  char *extraInfo = result + sz;
  char *extraAligned = (char *)alignPtr(extraInfo,EXTRA_INFO_ALIGN);

  *((unsigned int *)extraAligned) = sm->usedSz;

  sm->usedSz += sz+(extraAligned-extraInfo)+EXTRA_INFO_SZ;

  return result;
}

void *allocAlign(stackMem *sm, int sz, int align)
{
  align-=1;

  unsigned long resultTmp = (unsigned long) alloc(sm,sz+align);

  return alignPtr(resultTmp,align);
}

void dealloc(stackMem *sm)
{
  unsigned int *lastExtraInfo = (unsigned int *) (sm->mem + sm->usedSz - EXTRA_INFO_SZ);
  sm->usedSz = *lastExtraInfo;
}

#define MS 1024

void main(void)
{
  stackMem *sm = createStackMem(256,32);
  alloc(sm,128*MS);     //+
  alloc(sm,128*MS);     //++
  dealloc(sm);          //+
  alloc(sm,120*MS);     //++
  alloc(sm,8*MS);       //+++
  alloc(sm,1024*MS);    //++++
  dealloc(sm);          //+++
  alloc(sm,1023*MS);    //++++
  allocAlign(sm,1*MS,4);//+++++
  allocAlign(sm,1*MS,4);//++++++
  dealloc(sm);          //+++++
  dealloc(sm);          //++++
  dealloc(sm);          //+++
  dealloc(sm);          //++
  dealloc(sm);          //+
  dealloc(sm);          //
}

